//
// Description: 524. 通过删除字母匹配到字典里最长单词
// Created by Loading on 2021/9/14.
//

#include <bits/stdc++.h>

using namespace std;

string findLongestWord(string s, vector<string> &dictionary) {
    // 子序列结果集
    vector<string> strs;

    // 判断 temp 是否是 s 的子序列
    auto check = [&](string &temp) {
        int index = 0;
        for (int i = 0; i < s.size() && index < temp.size(); ++i) {
            if (s[i] == temp[index]) {
                ++index;
            }
        }
        if (index == temp.size()) {
            return true;
        }
        return false;
    };

    for (auto &str : dictionary) {
        if (check(str)) {
            // 是 s 的一个子序列，加入结果集
            strs.emplace_back(str);
        }
    }

    // 排序，长度一样按照字典序，否则长度长的优先
    sort(strs.begin(), strs.end(), [](const string &s1, const string &s2) {
        if (s1.size() == s2.size()) {
            return s1 < s2;
        }
        return s1.size() > s2.size();
    });

    if (strs.empty()) {
        return "";
    }
    return strs[0];
}

int main() {
    string s = "abpcplea";
    vector<string> dictionary = {"ale", "apple", "monkey", "plea"};
    string res = findLongestWord(s, dictionary);
    cout << res << endl;

    return 0;
}